hash 算法相关

hash 算法的意义在于把一个大的集合 A，映射到小的集合 B。最常见的就是 hash(key) = key % m 这种通过取余来获取 hash 值得方式。其中，m 就是模数。

显然，hash(key) 的取值范围是 [0,m-1]。

假设存在一个整数 x 使得 key % m = key - xm 成立。

即，key 在去掉 x 个 m 之后，剩下的比 m 小的部分就是 key % m 的值。

现在我们把

hash(key) = key - xm

变形为

hash(key) = gcd(key,m)*(key/gcd(key,m) - xm/gcd(key,m))

注: gcd 函数表示计算最大公约数

可知 hash(key) 的值只能是 gcd(key,m) 的倍数。这意味着在实际操作时，hash(key) 的值不一定能取到 [0,m-1] 上的所有值。

显然，gcd(key,m) 的值不为 1 时，hash(key) (即非 1 数的倍数) 一定不能取到 [0,m-1] 上的所有值。要想让 hash(key) 能取到 [0,m-1] 上的所有值，只能让 gcd(key,m) = 1。此时 hash(key) 的取值是 1 的倍数，然而任何数都是 1 的倍数，也就意味着 hash(key) 可以取到 [0,m-1] 上的所有值。

gcd(key,m) = 1 意味着，key 和 m 的最大公约数为 1。通常，在实际操作中，key 的取值无法被影响，但 m 的取值可以人为规定。

如果将 m 定为一个素数，那么除非 key 是 m 的倍数，否则 gcd(key,m) 的值永远为 1。这样可以尽可能地让 hash(key) 的值在 [1,m-1] 上均匀分布，避免 hash 碰撞。

计算机中的取余运算 (也称为模运算) 是一个相对耗时的操作，主要是除法运算耗时较长。但是，计算机上的位运算耗时较短。所以人们找到了一种特殊情况，在这种情况下，计算机可以将取余运算转化为位运算，以节省 CPU 算力:

模数 m = 2^n 时取余运算 key % m 会被转换为 AND 运算 key & (m - 1) 。

注意到 2^n 的二进制表示为 1 后接 n 个 0，而 2^n - 1 的二进制表示为 n 个 1。比如:

• 2^4 = 16，二进制表示为 10000
• 2^5 = 32，二进制表示为 100000
• 2^4 - 1 = 15，二进制表示为 1111
• 2^5 - 1 = 31，二进制表示为 11111

根据 AND 运算的逻辑 0 AND 1 = 0, 1 AND 1 = 1 可以知道，key 与二进制表示为 n 个 1 的数，从低位到高位，按位做 AND 运算就表示取 key 的二进制表示的 n 个低位。

例如，如果我们要计算 21 % 8:

8      = 01000
8 - 1  = 00111 = 7
21     = 10101
-------------
21 % 8 = 00101 = 5

可以看到:

• m = 8 = 2^3 的二进制表示是 1000，n 值为 3
• m - 1 = 7 的二进制表示是 111，高位补 0 变成 00111
• key = 21 的二进制表示是 10101
• key & (m - 1) 的效果是保留了从低位开始的 n 位，即，保留低 3 位得到 101 转十进制为 5